/*
 * @lc app=leetcode.cn id=1743 lang=typescript
 *
 * [1743] 从相邻元素对还原数组
 */

// @lc code=start
function restoreArray(adjacentPairs: number[][]): number[] {
  // 将每个点和对应的边存入哈希
  const hash: Map<number, number[]> = new Map();
  for (const adj of adjacentPairs) {
    const [from, to] = adj;
    hash.has(from) ? hash.get(from).push(to) : hash.set(from, [to]);
    hash.has(to) ? hash.get(to).push(from) : hash.set(to, [from]);
  }

  const ans: number[] = new Array(adjacentPairs.length + 1);
  // 当前点只有1个边表示这是一个起点或者终点，我们初始化一个，方便构建整个数组
  for (const [e, adj] of hash.entries()) {
    // 代表起点
    if (adj.length === 1) {
      ans[0] = e;
      break;
    }
  }
  ans[1] = hash.get(ans[0])[0];

  // 每个点的下一个点就是边中未被访问的点
  for (let i = 2; i < ans.length; i++) {
    const adj = hash.get(ans[i - 1]);
    ans[i] = ans[i - 2] === adj[0] ? adj[1] : adj[0];
  }

  return ans;
}
// @lc code=end
